import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.util.*;
import javax.swing.*;

public class SortLab {
	private SortDisplay display;

	public static void main(String[] args) {
		SortLab sorter = new SortLab();
	}

	public SortLab() {
		display = new SortDisplay(this);
	}

	public void bubbleSort(Comparable[] a) {
		for (int i = 0; i < a.length; i++)
			for (int j = 0; j + 1 < a.length - i; j++)
				if (a[j].compareTo(a[j + 1]) == 1)
					swap(j, j + 1, a);
	}

	// Postcondition: Returns the index of the minimum value from
	// a[startIndex] to end of array
	public int indexOfMin(Comparable[] a, int startIndex) {
		int minI = startIndex;
		for (int i = startIndex; i < a.length; i++)
			if (a[minI].compareTo(a[i]) == 1)
				minI = i;
		return minI;
	}

	public void selectionSort(Comparable[] a) {
		for (int i = 0; i < a.length; i++)
			swap(i, indexOfMin(a, i), a);
	}

	public void swap(int i, int j, Comparable[] a) {
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
		display.update();
	}

	// Precondition: a[0] to a[nextIndex - 1] are in increasing order
	// Postcondition: a[0] to a[nextIndex] are in increasing order
	public void insert(Comparable[] a, int nextIndex) {
		Comparable k = a[nextIndex];
		int j;
		for (j = nextIndex - 1; j >= 0 && a[j].compareTo(k) == 1; j--) {
			a[j + 1] = a[j];
		}
		a[j + 1] = k;
		display.update();
	}

	public void insertionSort(Comparable[] a) {
		for (int i = 0; i < a.length; i++) {
			insert(a, i);
		}
	}

	public void mergesort(Comparable[] a) {
		/* INSERT CALL TO mergesortHelp HERE */
		// #6
		mergesortHelp(a, 0, a.length - 1);
		display.update();
	}

	// Postcondition: a[lowIndex] to a[highIndex] are in increasing order
	private void mergesortHelp(Comparable[] a, int lowIndex, int highIndex) {
		/* INSERT RECURSIVE CODE HERE */
		// #6
		if (highIndex - lowIndex < 1)
			return;
		int mid = (lowIndex + highIndex) / 2;
		mergesortHelp(a, lowIndex, mid);
		display.update();
		mergesortHelp(a, mid + 1, highIndex);
		display.update();
		merge(a, lowIndex, mid, highIndex);
		display.update();
	}

	// Precondition: a[lowIndex] to a[midIndex] are in increasing order.
	// a[midIndex + 1] to a[highIndex] are in increasing order.
	// Postcondition: a[lowIndex] to a[highIndex] are in increasing order.
	private void merge(Comparable[] a, int lowIndex, int midIndex, int highIndex) {
		Comparable[] copy = new Comparable[a.length];
		for (int i = lowIndex; i <= highIndex; i++)
			copy[i] = a[i];
		int left = lowIndex;
		int right = midIndex + 1;
		for (int i = lowIndex; i <= highIndex; i++) {
			if (right > highIndex
					|| (left <= midIndex && copy[left].compareTo(copy[right]) < 0)) {
				a[i] = copy[left];
				left++;
			} else {
				a[i] = copy[right];
				right++;
			}
		}
		display.update();
	}

	// Postcondition: a[lowIndex] to a[highIndex] are in increasing order
	public void quicksort(Comparable[] a) {
		/* INSERT CALL TO quicksortHelp HERE */
		// #7
		quicksortHelp(a, 0, a.length - 1);
		display.update();
	}

	// performs quicksort on portion of array from lowIndex to highIndex
	private void quicksortHelp(Comparable[] a, int lowIndex, int highIndex) {
		/* INSERT RECURSIVE CODE HERE */
		// #7
		if (lowIndex >= highIndex)
			return;
		int part = partition(a, lowIndex, highIndex);
		display.update();
		quicksortHelp(a, lowIndex, part);
		display.update();
		quicksortHelp(a, part + 1, highIndex);
		display.update();
	}

	// Postcondition: Returns the index of the pivot element.
	// All elements on the left side of the pivot (from lowIndex)
	// are less than or equal to the pivot.
	// All elements on the right side of the pivot (through highIndex)
	// are greater than or equal to the pivot.
	private int partition(Comparable[] a, int lowIndex, int highIndex) {
		int pivot = lowIndex;
		for (int unsorted = lowIndex + 1; unsorted <= highIndex; unsorted++) {
			if (a[unsorted].compareTo(a[pivot]) < 0) {
				Comparable temp = a[pivot];
				a[pivot] = a[unsorted];
				a[unsorted] = a[pivot + 1];
				a[pivot + 1] = temp;
				pivot++;
				display.update();
			}
		}
		return pivot;
	}
}

class SortDisplay extends JButton implements ActionListener {
	private static Random random = new Random();

	private Comparable[] array; // array modified by the user
	private int[] oldPointers; // where each arrow used to point
	private int[] pointers; // where each arrow points
	private Object[] oldObjects; // old arrangements of objects
	private Object[] objects; // objects ordered by position on screen
	private boolean clicked;
	private boolean isCancellingSort = true;
	private SortLab sorter;
	private JButton selectionButton;
	private JButton insertionButton;
	private JButton mergeButton;
	private JButton quickButton;
	private JButton bubbleButton;

	public SortDisplay(SortLab sorter) {
		this.sorter = sorter;

		// createArray();

		JFrame frame = new JFrame();
		frame.setTitle("Sort Display");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.getContentPane().setLayout(
				new BoxLayout(frame.getContentPane(), BoxLayout.PAGE_AXIS));

		selectionButton = new JButton("Start Selection Sort");
		selectionButton.setAlignmentX(Component.LEFT_ALIGNMENT);
		selectionButton.setMnemonic(KeyEvent.VK_L);
		selectionButton.setActionCommand("selection");
		selectionButton.addActionListener(this);
		frame.getContentPane().add(selectionButton);

		insertionButton = new JButton("Start Insertion Sort");
		insertionButton.setAlignmentX(Component.LEFT_ALIGNMENT);
		insertionButton.setMnemonic(KeyEvent.VK_I);
		insertionButton.setActionCommand("insertion");
		insertionButton.addActionListener(this);
		frame.getContentPane().add(insertionButton);

		mergeButton = new JButton("Start Mergesort");
		mergeButton.setAlignmentX(Component.LEFT_ALIGNMENT);
		mergeButton.setMnemonic(KeyEvent.VK_M);
		mergeButton.setActionCommand("merge");
		mergeButton.addActionListener(this);
		frame.getContentPane().add(mergeButton);

		quickButton = new JButton("Start Quicksort");
		quickButton.setAlignmentX(Component.LEFT_ALIGNMENT);
		quickButton.setMnemonic(KeyEvent.VK_Q);
		quickButton.setActionCommand("quick");
		quickButton.addActionListener(this);
		frame.getContentPane().add(quickButton);

		bubbleButton = new JButton("Start Bubble Sort");
		bubbleButton.setAlignmentX(Component.LEFT_ALIGNMENT);
		bubbleButton.setMnemonic(KeyEvent.VK_B);
		bubbleButton.setActionCommand("bubble");
		bubbleButton.addActionListener(this);
		frame.getContentPane().add(bubbleButton);

		setAlignmentX(Component.LEFT_ALIGNMENT);
		setMinimumSize(new Dimension(200, 200));
		setPreferredSize(new Dimension(600, 400));
		setMaximumSize(new Dimension(Integer.MAX_VALUE, Integer.MAX_VALUE));
		setActionCommand("step");
		addActionListener(this);
		frame.getContentPane().add(this);

		JButton stepButton = new JButton("Step");
		stepButton.setAlignmentX(Component.LEFT_ALIGNMENT);
		stepButton.setMnemonic(KeyEvent.VK_S);
		stepButton.setActionCommand("step");
		stepButton.addActionListener(this);
		frame.getContentPane().add(stepButton);

		frame.pack();
		frame.setVisible(true);

		startSort("selection");
	}

	protected void paintComponent(Graphics g) {
		if (pointers == null)
			return;

		Graphics2D g2 = (Graphics2D) g;
		g2.setColor(Color.WHITE);
		g2.fill(new Rectangle2D.Double(0, 0, getWidth(), getHeight()));
		g2.setColor(Color.BLACK);
		int unit = getWidth() / pointers.length;
		FontMetrics metrics = g2.getFontMetrics();
		for (int i = 0; i < array.length; i++) {
			g2.setColor(Color.BLACK);
			g2.draw(new Rectangle2D.Double(i * unit, 0, unit, unit));
			if (pointers[i] == oldPointers[i])
				g2.setColor(Color.BLUE);
			else
				g2.setColor(Color.RED);
			g2.draw(new Line2D.Double(i * unit + unit / 2, unit / 2,
					pointers[i] * unit + unit / 2, 2 * unit));
			if (objects[i] == oldObjects[i])
				g2.setColor(Color.BLUE);
			else
				g2.setColor(Color.RED);
			String text = objects[i].toString();
			g2.drawString(text, i * unit + unit / 2 - metrics.stringWidth(text)
					/ 2, 2 * unit + metrics.getAscent());
		}
	}

	private int indexOf(Object x) {
		for (int i = 0; i < objects.length; i++)
			if (objects[i] == x)
				return i;
		return -1;
	}

	public void update() {
		// check if anything changed
		boolean changed = false;
		for (int i = 0; i < array.length; i++) {
			if (array[i] != objects[pointers[i]]) {
				changed = true;
				break;
			}
		}
		if (!changed)
			return;

		// save old positions
		for (int i = 0; i < array.length; i++) {
			oldPointers[i] = pointers[i];
			oldObjects[i] = objects[i];
		}

		// find new positions from array
		for (int i = 0; i < array.length; i++)
			pointers[i] = indexOf(array[i]);

		redraw();

		// save old positions
		for (int i = 0; i < array.length; i++) {
			oldPointers[i] = pointers[i];
			oldObjects[i] = objects[i];
		}

		// find ways to reduce arrow length by swapping objects.
		changed = false;
		for (int i = 0; i < array.length; i++)
			for (int j = i + 1; j < array.length; j++) {
				int iIndex = pointers[i];
				int jIndex = pointers[j];

				// find total length of all arrows, before and after
				int oldLength = 0;
				for (int k = 0; k < array.length; k++)
					oldLength += Math.abs(k - pointers[k]);
				int newLength = 0;
				for (int k = 0; k < array.length; k++) {
					int target = pointers[k];
					if (target == iIndex)
						target = jIndex;
					else if (target == jIndex)
						target = iIndex;
					newLength += Math.abs(k - target);
				}

				if (newLength < oldLength) {
					changed = true;

					// should change ANY pointer that points to either of these
					// two objects
					for (int k = 0; k < array.length; k++) {
						if (pointers[k] == iIndex)
							pointers[k] = jIndex;
						else if (pointers[k] == jIndex)
							pointers[k] = iIndex;
					}

					Object object = objects[iIndex];
					objects[iIndex] = objects[jIndex];
					objects[jIndex] = object;
				}
			}

		if (!changed)
			return;

		redraw();
	}

	private void redraw() {
		if (isCancellingSort)
			return;

		repaint();

		clicked = false;
		while (!clicked)
			try {
				Thread.sleep(100);
			} catch (InterruptedException e) {
			}
	}

	public void actionPerformed(ActionEvent e) {
		final String action = e.getActionCommand();
		if (action.equals("step"))
			clicked = true;
		else
			startSort(action);
	}

	private void startSort(final String action) {
		Thread thread = new Thread() {
			public void run() {
				// finish current sort
				isCancellingSort = true;
				clicked = true;
				try {
					Thread.sleep(100);
				} catch (InterruptedException e) {
				}
				isCancellingSort = false;

				resetButtons();

				if (action.equals("selection")) {
					selectionButton.setForeground(Color.GREEN.darker());
					createArray();
					sorter.selectionSort(array);
				} else if (action.equals("bubble")) {
					bubbleButton.setForeground(Color.GREEN.darker());
					createArray();
					sorter.bubbleSort(array);
				} else if (action.equals("insertion")) {
					insertionButton.setForeground(Color.GREEN.darker());
					createArray();
					sorter.insertionSort(array);
				} else if (action.equals("merge")) {
					mergeButton.setForeground(Color.GREEN.darker());
					createArray();
					sorter.mergesort(array);
				} else if (action.equals("quick")) {
					quickButton.setForeground(Color.GREEN.darker());
					createArray();
					sorter.quicksort(array);
				} else
					throw new UnsupportedOperationException(action);
			}
		};
		thread.start();
	}

	private void resetButtons() {
		selectionButton.setForeground(null);
		insertionButton.setForeground(null);
		mergeButton.setForeground(null);
		quickButton.setForeground(null);
		bubbleButton.setForeground(null);
	}

	private void createArray() {
		String[] strings = { "alpha", "bravo", "charlie", "delta", "echo",
				"foxtrot", "golf", "hotel", "india", "juliet", "kilo", "lima" };
		Integer[] integers = new Integer[12];
		for (int i = 0; i < integers.length; i++)
			integers[i] = new Integer(i + 1);
		Double[] doubles = { new Double(1), new Double(1.059),
				new Double(1.122), new Double(1.189), new Double(1.260),
				new Double(1.335), new Double(1.414), new Double(1.498),
				new Double(1.587), new Double(1.682), new Double(1.782),
				new Double(1.888), new Double(2) };
		MyLocation[] locs = { new MyLocation(1, 1), new MyLocation(1, 2),
				new MyLocation(2, 1), new MyLocation(2, 2),
				new MyLocation(1, 3), new MyLocation(2, 3),
				new MyLocation(3, 1), new MyLocation(3, 2),
				new MyLocation(3, 3), new MyLocation(1, 4),
				new MyLocation(2, 4), new MyLocation(3, 4) };
		int choice = random.nextInt(4);
		Comparable[] copyFrom;
		if (choice == 0)
			copyFrom = strings;
		else if (choice == 1)
			copyFrom = integers;
		else if (choice == 2)
			copyFrom = doubles;
		else
			copyFrom = locs;
		array = new Comparable[random.nextInt(5) + 8];
		for (int i = 0; i < array.length; i++)
			array[i] = copyFrom[i];
		for (int i = 0; i < array.length; i++) {
			int j = random.nextInt(array.length - i) + i;
			Comparable temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
		pointers = new int[array.length];
		oldPointers = new int[array.length];
		objects = new Object[array.length];
		oldObjects = new Object[array.length];
		for (int i = 0; i < array.length; i++) {
			pointers[i] = i;
			oldPointers[i] = i;
			objects[i] = array[i];
			oldObjects[i] = array[i];
		}
		redraw();
	}
}

class MyLocation implements Comparable {
	private int row;
	private int col;

	public MyLocation(int r, int c) {
		row = r;
		col = c;
	}

	public int getRow() {
		return row;
	}

	public int getCol() {
		return col;
	}

	public boolean equals(Object x) {
		MyLocation other = (MyLocation) x;
		return row == other.getRow() && col == other.getCol();
	}

	public String toString() {
		return "(" + row + ", " + col + ")";
	}

	public int compareTo(Object x) {
		MyLocation other = (MyLocation) x;
		if (getRow() > other.getRow())
			return 1;
		if (getRow() < other.getRow())
			return -1;
		if (getCol() > other.getCol())
			return 1;
		if (getCol() < other.getCol())
			return -1;
		return 0;
	}
}